
/*
 * 	graph.c
 */

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "../inc/graph.h"
#include "../inc/priorityQueue.h"
#include "../inc/stack.h"
#include "../inc/log.h"
#include "../inc/defs.h"

/*
 *	Defines
 */

#define	HIGHER	1
#define	LOWER	-1
#define EQUAL	0
#define	OK		1
#define	TAGGED	1

typedef struct nodeCDT *nodeADT;
typedef struct edgeCDT *edgeADT;


struct graphCDT
{
	nodeADT first;			/* Lista de nodos */
	nodeCmpFn nCmp;
	nodeCpyFn nCpy;
	nodeFreeFn nFree;
	nodeADT nactual;
	edgeADT	eactual;

	edgeCpyFn eCpy;
	edgeFreeFn eFree;
	edgeWeightFn eWeight;	/* Funcion que evalua el peso de una arista */
	int qtyNodes;
	int qtyEdge;
	pqueueADT pqueue;
	stackADT stack;

};

typedef struct nodeCDT
{
	nodeElementT info;	/* dato de un nodo */
	int distance;
	nodeADT previous;	/* Puntero al nodo anterior, para dijkstra */
	edgeADT adyac;
	nodeADT nextNode;
	int tag;
}nodeCDT;

typedef struct edgeCDT
{
	edgeElementT info;
	nodeADT node;		/* Puntero a la cabeza de la arista */
	edgeADT nextEdge;
}edgeCDT;

static nodeADT InsertNode( graphADT graph, nodeADT *node,  nodeElementT data );
static int InsertEdge( graphADT graph, nodeADT nodeHead, edgeADT *edge, edgeElementT data );
static nodeADT FindNode( graphADT graph, nodeADT node, nodeElementT data );
static int deleteEdge( graphADT graph, edgeADT *edge, nodeElementT head );
static void deleteConection( graphADT graph, nodeADT node, nodeElementT data );
static int deleteNode( graphADT graph, nodeADT *node, nodeElementT data );
static void FreeEdgesAdy( graphADT graph, edgeADT * edge );
static void FreeNodes( graphADT graph, nodeADT node );
static edgeElementT WrapperOrigEdge( graphADT graph, edgeADT edge, nodeElementT head );
static int WrapperGetEdge( graphADT graph, edgeADT edge, nodeElementT head, edgeElementT *data );
static int Dijkstra( graphADT graph, nodeADT src, nodeADT tgt );
static void InitDistances(graphADT graph, nodeADT node, nodeADT first, int cantNodes);
static int stackPath(stackADT stack, nodeADT node);

graphADT
NewGraph( nodeCmpFn nCmp, nodeCpyFn nCpy, nodeFreeFn nFree, edgeCpyFn eCpy, edgeFreeFn eFree )
{
	graphADT aux;

	if( ( aux = malloc( sizeof(struct graphCDT) ) ) == NULL )
	{
		Fatal("NewGraph@graphADT.c - not enough memory\n");
		return NULL;
	}

	if( nCmp == NULL || nCpy == NULL || nFree == NULL || eCpy == NULL || eFree == NULL )
	{
		Error("NewGraph@graphADT.c - invalid arguments\n");
		return NULL;
	}

	aux -> first = NULL;
	aux -> nCmp = nCmp;
	aux -> nCpy = nCpy;
	aux -> nFree = nFree;
	aux -> eCpy = eCpy;
	aux -> eFree = eFree;
	aux -> eWeight = NULL;		
	aux -> qtyNodes = 0;		/* Cantidad de nodos */
	aux -> qtyEdge = 0;			/* Cantidad de aristas */
	aux -> pqueue = NULL;
	aux -> stack = NULL;

	return aux;
}

int
GraphIsEmpty( graphADT graph )
{
	if( graph == NULL )
	{
		Error("GraphIsEmpty@graphADT.c - invalid arguments\n");
		return 0;
	}

	return( graph -> qtyNodes == 0 );

}


int
NewNode( graphADT graph, nodeElementT node )
{
	if( graph == NULL )
		return 0;
	

	return ( InsertNode( graph, &graph -> first, node ) != NULL );
}

static nodeADT
InsertNode( graphADT graph, nodeADT *node,  nodeElementT data )
{
	nodeADT aux;
	int comp;


	/*	Si el grafo esta vacio( pq no tiene nodos o porque
	 *	recursivamente se llego al final de la lista ) se inserta
	 *	ahi, de lo contrario, en el lugar que corresponda
	 */

	if( *node == NULL )
		comp = HIGHER;
	else
		comp =  graph -> nCmp ( (*node) -> info, data ) ;

	if( comp > 0 )
	{
		aux = *node;

		if( ( *node = malloc( sizeof( nodeCDT ) ) ) == NULL )
		{
			Fatal("NewNode@graphADT.c - not enough memory\n");
			Debug("InsertNode@graphADT.c - failed to alloc memory for new node\n");
			return NULL;
		}

		if( graph -> nCpy ( &(*node) -> info , data ) != OK )
		{
			Fatal("NewNode@graphADT.c - call back node copy function failed\n");
			return NULL;
		}

		(*node ) -> distance = 0;
		(*node) -> previous = NULL;		
		(*node) -> adyac = NULL;
		(*node) -> nextNode = aux;		
		(*node) -> tag = !TAGGED;

		graph -> qtyNodes++;

		return *node;

	}

	else
	{
		if( comp < 0 )
			return InsertNode( graph, &(*node) -> nextNode, data );
		else
		{
			/* Si ya existe, actualiza el dato */
			graph -> nFree( (*node) -> info );	
			graph -> nCpy( &(*node) -> info, data);
			return *node;	/* Si son iguales el nodo ya existia */
		}
	}
}


static void
unMark( nodeADT node )
{
	if( node != NULL )
	{
		node -> distance = 0;
		node -> previous = NULL;
		node -> tag = 0;

		unMark( node -> nextNode );
	}
}

int
NewArc( graphADT graph, nodeElementT tail, nodeElementT head, edgeElementT data )
{
	nodeADT nodeTail, nodeHead;
	int comp;

	if( graph == NULL || tail == NULL || head == NULL )
	{
		Error("NewArc@graphADT.c - invalid arguments\n");
		return 0;
	}

	/* Como la lista es ordenada se busca primero el menor y una vez encontrado
	 * ( o insertado si es que no existia ), busca a partir de alli el otro
	 */

	comp = graph -> nCmp (tail, head );

	/* Caso que tail < head */

	if( comp < 0 )
	{
		nodeTail = FindNode( graph, graph -> first, tail );
		nodeHead = FindNode( graph, nodeTail, head );
	}

	else
	{
		nodeHead = FindNode( graph, graph -> first, head );
		nodeTail = FindNode( graph, nodeHead, tail );
	}

	if( nodeTail == NULL || nodeHead == NULL )
	{
		return 0;
	}

	/* nodeHead es el nodo con el que se lo quiere conectar
	 * nodeTail -> adyac es el nodo que esta en la estructura y
	 * 				apunta al primer nodo en la lista de ady.
	 */
	return InsertEdge( graph, nodeHead, &nodeTail -> adyac, data );
}

static nodeADT
FindNode( graphADT graph, nodeADT node, nodeElementT data )
{
	int comp;


	/* Si el nodo es NULL o el dato buscado es menor que
	 * el que se encuentra en el nodo se genera un error
	 * y retorna NULL
	 */

	if( node == NULL )
	   return NULL;

	else
	{

		comp = graph -> nCmp ( node -> info, data );

		if( comp < 0 )
			return FindNode( graph, node -> nextNode, data );

		/* Si la comparacion es > 0 significa que no se encontro el nodo */
		else if (comp > 0)
			return NULL;

		return node;
	}
}

static int
InsertEdge( graphADT graph, nodeADT nodeHead, edgeADT *edge, edgeElementT data )
{
	edgeADT aux;
	int comp = HIGHER;


	if( (*edge ) == NULL || ( comp = graph -> nCmp( (*edge ) -> node -> info, nodeHead -> info ) ) >= 0 )
	{

		aux = *edge;

		if( ( *edge = malloc( sizeof( edgeCDT ) ) ) == NULL )
		{
			Fatal("NewArc@graphADT.c - not enough memory\n");
			Debug("InsertEdge@graphADT.c - memory alloc for a new edge failed\n");
			return 0;
		}

		if(graph -> eCpy( &( *edge) -> info, data )  == 0 )
		{
			Fatal("NewArc@graphADT.c - not enough memory\n");
			Debug("InsertEdge@graphADT.c - call back edge copy function failed\n");
			return 0;
		}

		( *edge ) -> node = nodeHead;
		(*edge ) -> nextEdge = aux;

		graph -> qtyEdge++;

		if( comp == EQUAL )
			graph -> eFree( aux -> info );

	}
	else
		if( comp < 0 )
			return InsertEdge( graph, nodeHead, &(*edge ) -> nextEdge, data );

	return OK;
}


int
removeEdge( graphADT graph, nodeElementT tail, nodeElementT head )
{
	nodeADT auxTail;

	if( graph == NULL || tail == NULL || head == NULL )
	{
		Error("removeEdge@graphADT.c - invalid arguments\n");
		return 0;
	}

	auxTail = FindNode( graph, graph -> first, tail );

	if( auxTail == NULL )
	{
		Error("removeEdge@graphADT.c - invalid tail node\n");
		return 0;
	}

	return deleteEdge( graph, &auxTail -> adyac, head );

}

static int
deleteEdge( graphADT graph, edgeADT *edge, nodeElementT head )
{
	int comp;


	if( ( *edge) == NULL ||	( comp = graph -> nCmp( (*edge) -> node -> info, head ) ) > 0 )
		return 0;

	else
	{
		if( comp < 0 )
			return deleteEdge( graph, &(*edge) -> nextEdge, head );
		else
		{
			/* Arista a borrar encontrada! */
			edgeADT edgeAux;

			edgeAux = (*edge);

			(*edge) = (*edge) -> nextEdge;

			graph -> eFree( edgeAux -> info );
			free( edgeAux );

			graph -> qtyEdge--;
		}
	}

	return OK;
}

int
removeNode( graphADT graph, nodeElementT data )
{
	if( graph == NULL || data == NULL )
	{
		Error("removeNode@graphADT.c - invalid arguments\n");
		return 0;
	}

	/* Primero borra las conexiones de la lista
	 * de adyacencia, es decir saca la arista que
	 * une a un nodo con el que se quiere borrar.
	 */

	deleteConection( graph, graph -> first, data );

	return deleteNode( graph, &graph -> first, data );
}

static void
deleteConection( graphADT graph, nodeADT node, nodeElementT data )
{
	if( node == NULL )
		return;
	
	deleteConection( graph, node -> nextNode, data );
	   
	deleteEdge( graph, &node -> adyac, data );

	
}
static int
deleteNode( graphADT graph, nodeADT *node, nodeElementT data )
{
	int comp;

	if( (*node) == NULL || ( comp = graph -> nCmp( (*node) -> info, data ) ) > 0 )
	{
		Error("removeNode@graphADT.c - node does not exist\n");
		return 0;
	}

	else
	{
		if( comp < 0 )
			return deleteNode( graph, &(*node) -> nextNode, data );
		else
		{
			/* Nodo a borrar encontrado */
			nodeADT nodeAux;

			nodeAux = (*node);

			(*node) = (*node) -> nextNode;
			FreeEdgesAdy( graph, &nodeAux -> adyac );
			graph -> nFree( nodeAux -> info );
			free( nodeAux );
			graph -> qtyNodes--;
		}
	}

	return OK;
}

static void
FreeEdgesAdy( graphADT graph, edgeADT * edge )
{
	if( (*edge) == NULL )
		return;
		
	FreeEdgesAdy( graph, &(*edge) -> nextEdge );

	graph -> eFree( (*edge) -> info);
	free( (*edge) );
	(*edge) = NULL;
}


int
elementBelongs( graphADT graph, nodeElementT data )
{
	if( graph == NULL || data == NULL )
	{
		Error("elementBelongs@graphADT.c - invalid arguments\n");
		return 0;
	}

	return ( FindNode( graph, graph -> first, data ) != NULL );
}

void
FreeGraph( graphADT graph )
{
	if( graph != NULL )
	{
		FreeNodes( graph, graph -> first );
		free( graph );
	}
}

static void
FreeNodes( graphADT graph, nodeADT node )
{
	if( node == NULL )
		return;
		
	FreeNodes( graph, node -> nextNode );
	FreeEdgesAdy( graph, &node -> adyac );
	graph -> nFree( node -> info );
	free( node );
	return;
}

edgeElementT 
GetOriginalEdge(graphADT graph, nodeElementT tail, nodeElementT head)
{
	nodeADT nodeTail;
	edgeADT edge;
	
	if( graph == NULL )
	{
		Error("GetEdge@graphADT.c - invalid arguments\n");
		return NULL;
	}

	nodeTail = FindNode( graph, graph -> first, tail);

	if( nodeTail == NULL)
	{
		Error("GetEdge@graphADT.c - invalid tail node\n");
		return NULL;
	}

	/* Si ese nodo no tiene adyacentes, retorna NULL */
	if ( (edge = nodeTail -> adyac) == NULL )
		return NULL;
	
	return WrapperOrigEdge(graph, edge, head);
}

static edgeElementT
WrapperOrigEdge( graphADT graph, edgeADT edge, nodeElementT head )
{
	int comp = 1;
	comp = graph -> nCmp( edge -> node -> info, head  );

	if( comp < 0 && edge -> nextEdge != NULL)
		return WrapperOrigEdge( graph, edge -> nextEdge, head );
	else
	{
		/* si la comparacion es 0, encontre la arista que se quiere retornar */
		if( comp == 0 )
			return edge -> info;
		else /* Si llega aqui quiere decir que la arista o no existe o no son adyacentes los nodos */
			return NULL;
	}
}	

int
GetEdge(graphADT graph, nodeElementT tail, nodeElementT head, edgeElementT * data)
{
	nodeADT nodeTail;
	edgeADT edge;


	if( graph == NULL )
	{
		Error("GetEdge@graphADT.c - invalid arguments\n");
		return 0;
	}

	nodeTail = FindNode( graph, graph -> first, tail);

	if( nodeTail == NULL)
	{
		Error("GetEdge@graphADT.c - invalid tail node\n");
		*data = NULL;
		return 0;
	}

	/* Si ese nodo no tiene adyacentes, retorna 0 */
	if ( (edge = nodeTail -> adyac) == NULL )
		return 0;

	return WrapperGetEdge( graph, edge, head, data );
}

static int
WrapperGetEdge( graphADT graph, edgeADT edge, nodeElementT head, edgeElementT *data )
{
	int comp = 1;
	comp = graph -> nCmp( edge -> node -> info, head  );


	/* Si el nodo al que apunta la arista es < al nodo buscado, y hay mas nodos adyacentes,
	 * continua la busqueda */
	if( comp < 0 && edge -> nextEdge != NULL)
		return WrapperGetEdge( graph, edge -> nextEdge, head, data );
	else
	{
		/* si la comparacion es 0, arista encontrada */
		if( comp == 0 )
		{
			if( graph -> eCpy( data, edge -> info )  != OK )
			{
				/* Error al copiar bla bla */
				return 0;
			}

			return 1;
		}
		else /* Si llega aqui quiere decir que la arista o no existe o no son adyacentes los nodos */
			return 0;
	}
}

static void
WrapperRemove( graphADT graph, nodeADT node )
{
	if( node == NULL )
		return;
		
	WrapperRemove( graph, node -> nextNode );
	FreeEdgesAdy( graph, &node -> adyac );
	
}

void
removeAllEdges( graphADT graph )
{
	WrapperRemove( graph, graph -> first );
	graph -> qtyEdge = 0;
}

/********* DIJKSTRA ********************/

int
SetBeginDijkstra( graphADT graph, nodeElementT src, nodeElementT tgt )
{
	nodeADT nodeSrc;
	nodeADT nodeTgt;
	int dijok;

	if( graph == NULL)
	{
		Error("SetBeginDijkstra@graphADT.c - invalid graph instance\n");
		return 0;
	}

	if( GraphIsEmpty( graph))
	{
		Error("SetBeginDijkstra@graphADT.c - empty graph\n");
		return 0;
	}

	if ( ( graph -> pqueue = NewPQueue() ) == NULL )
	{
		Fatal("SetBeginDijkstra@graphADT.c - not enough memory\n");
		return 0;
	}

	if( ( graph -> stack = NewStack()) == NULL )
	{
		Fatal("SetBeginDijkstra@graphADT.c - not enough memory\n");
		return 0;

	}


	unMark(graph -> first);
	nodeSrc = FindNode( graph, graph -> first, src);
	nodeTgt = FindNode( graph, graph -> first, tgt);

	if( nodeSrc != NULL && nodeTgt != NULL && nodeSrc != nodeTgt)
	{	
		if ( (dijok = Dijkstra( graph, nodeSrc, nodeTgt)) == 0 || dijok == PATHERROR)
		{
			FreePQueue(graph -> pqueue);
			FreeStack(graph -> stack);
			graph -> pqueue = NULL;
			graph -> stack = NULL;
			return dijok;
		}
		return 1;
	}

	FreePQueue(graph -> pqueue);
	FreeStack(graph -> stack);
	graph -> pqueue = NULL;
	graph -> stack = NULL;
	return 0;

}

edgeElementT
GetNextDijkstraEdge(graphADT graph)
{
	edgeElementT aux1, rta;

	if ( Precondicion(graph) )
	{
		Error("GetNextDijkstraEdge@graphADT.c - invalid arguments\n");
		return NULL;
	}

	if ( GraphIsEmpty(graph) )
	{
		Debug("GetNextDijkstraEdge@graphADT.c - empty graph\n");
		return NULL;
	}

	if (graph -> stack == NULL )
	{
		Error("GetNextDijkstraEdge@graphADT.c - Invoke SetBeginDijkstra first\n");
		return NULL;
	}

	if (StackIsEmpty(graph -> stack))
	{
		Debug("GetNextDijkstraEdge@graphADT.c - dijkstra stack emptied\n");
		FreeStack(graph -> stack);
		graph -> stack = NULL;
		return NULL;
	}

	/* Obtiene proxima arista del camino minimo */
	aux1 = Pop(graph -> stack);

	if (aux1 != NULL )
	{
		if (!graph -> eCpy(&rta, aux1))
		{
			Fatal("GetNextDijkstraEdge@graphADT.c - not enough memory\n");
			Push(graph -> stack, aux1); /* si falla vuelvo a meter la arista al stack */
			return NULL;
		}
	}
	else
	{
		FreeStack(graph -> stack);
		graph -> stack = NULL;
		return NULL;
	}

	return rta;
}

static int
Dijkstra( graphADT graph, nodeADT src, nodeADT tgt )
{
	int pathEnd=0, weight;
	nodeADT node, nodeU, nodeV/*, ndeqaux*/;
	edgeADT nodeAdy;
	edgeWeightFn eweight;

	if (graph == NULL || src == NULL || tgt == NULL)
		return 0;

	/* Se inicializan todos los nodos del grafo
	 * La distancia de cada nodo es infinita y los padres son NULL */

	node = graph->first;
	/* Inicia distancias y encola todos los nodos excepto el src */
	InitDistances(graph, node, src, graph -> qtyNodes);
	PEnqueue(graph -> pqueue, src, src -> distance);

	eweight = graph->eWeight;

	while ( !pathEnd && !PQueueIsEmpty(graph -> pqueue) )
	{
		nodeU = PDequeue(graph -> pqueue);
		
		nodeU -> tag = 1; /* Para evitar ciclos */

		if (nodeU == tgt)
			pathEnd=1;


		nodeAdy = nodeU -> adyac;
		/* si el nodo desencolado tiene adyacencias, evalua el peso del camino a cada vecino */
		if (!pathEnd && nodeAdy != NULL)
		{
			for (nodeAdy = nodeU -> adyac ; nodeAdy != NULL ; nodeAdy = nodeAdy->nextEdge)
			{
				nodeV=nodeAdy->node;
				if ( !nodeV -> tag && nodeV->distance > nodeU->distance + (weight = eweight(nodeAdy->info)))
				{
					if (weight == -1)
						return 0;
					/* Actualiza distancia total al nodo en el camino minimo y su nodo previo */
					nodeV -> distance = nodeU -> distance + weight;
					nodeV -> previous = nodeU;
					/* Encola */
					PEnqueue(graph -> pqueue, nodeV, nodeV -> distance);
				}
			}
		}
	}

	if (!pathEnd)
		return PATHERROR;

	node = tgt;

	if ( !stackPath(graph->stack, node) )
	{
		graph->stack = NULL;
		return 0;
	}

	FreePQueue(graph -> pqueue);
	graph -> pqueue = NULL;

	return 1;
}

static void
InitDistances(graphADT graph, nodeADT node, nodeADT first, int cantNodes)
{
	int i;

	for (i=0; i<cantNodes; i++)
	{
		if (node != first)
		{
			node->distance = INT_MAX;
			node->previous = NULL;
			node = node->nextNode;
		}
		else
		{
			node -> distance = 0;
			node -> previous = NULL;
			node = node->nextNode;
		}
	}
	return;
}

static int
stackPath(stackADT stack, nodeADT node)
{
	edgeADT nodeAdy;

	while (node->previous != NULL)
	{
		nodeAdy = node->previous->adyac;
		
		/* Busca la arista que conecta al nodo previo con el actual */
		while(nodeAdy -> node != node)
			nodeAdy = nodeAdy -> nextEdge;
			
		/* Esa es la que finalmente va al stack */
		if ( !Push(stack, nodeAdy->info) )
		{
			FreeStack(stack);
			return 0;
		}
		node = node->previous;
	}

	return 1;
}

int
SetNodeIterator(graphADT graph)
{
	if (Precondicion(graph))
		return 0;

	graph->nactual = graph->first;

	return 1;
}

nodeElementT
GetNextNode(graphADT graph)
{
	nodeElementT aux;

	if ( Precondicion(graph) || Precondicion(graph->nactual) )
		return NULL;

	aux = graph->nactual->info;

	graph->nactual = graph->nactual->nextNode;

	return aux;
}

int
SetEdgeIterator(graphADT graph, nodeElementT src)
{
	nodeADT node;

	if ( Precondicion(graph) || Precondicion(src))
		return 0;


	if ( (node = FindNode(graph, graph -> first, src)) == NULL )
	{
		Error("SetEdgeIterator@graphADT.c - source node does not exist, can not initiate edge iterator\n");
		return 0;
	}

	graph->eactual = node -> adyac;

	return 1;
}

int
GetNextEdge(graphADT graph, nodeElementT src, edgeElementT *edge, nodeElementT *tgt)
{
	nodeADT nodesrc;

	if ( Precondicion(graph) || Precondicion(src) || Precondicion(edge) || Precondicion(tgt) )
		return 0;

	if ( (nodesrc = FindNode(graph, graph->first, src) ) == NULL )
		return 0;

	if (graph -> eactual != NULL)
	{
		*edge = graph -> eactual -> info;
		*tgt = graph -> eactual -> node -> info;
		graph -> eactual = graph -> eactual -> nextEdge;
	}
	else
		return 0;

	return 1;
}

nodeElementT* getNodesInfo(graphADT graph, int * n) {
	nodeElementT * airports;
	nodeADT node;
	int i;
	
	airports = malloc(graph->qtyNodes * sizeof(nodeElementT));
	node = graph->first;
	
	for (i = 0; i < graph->qtyNodes ; i++) {
		airports[i] = node->info;
		node = node->nextNode; 
	}
	*n = graph->qtyNodes;
	return airports;
}

void
SetWeightFunction(graphADT graph, edgeWeightFn fnW)
{
	if ( Precondicion(graph) || Precondicion(fnW) )
	{
		Error("SetWeight@graphADT.c - invalid arguments\n");
		return;
	}

	graph->eWeight = fnW;
}
